package pers.qianyu.month_202102.date_20210212;

import java.util.*;

/**
 * 119. 杨辉三角 II
 * https://leetcode-cn.com/problems/pascals-triangle-ii/
 *
 * @author mizzle rain
 * @date 2021-02-12 23:35
 */
public class GetRow {
    // 最原始版本
    public List<Integer> getRow0(int rowIndex) {
        ArrayList<Integer> pre = new ArrayList<>();
        ArrayList<Integer> cur = new ArrayList<>();
        pre.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = 0, size = pre.size(); j < size + 1; j++) {
                if (j == 0 || j == size) {
                    cur.add(1);
                } else {
                    cur.add(pre.get(j - 1) + pre.get(j));
                }
            }
            pre = cur;
            cur = new ArrayList<>();
        }
        return pre;
    }

    // 滚动数组优化版本
    public List<Integer> getRow1(int rowIndex) {
        ArrayList<Integer> cur = new ArrayList<>();
        cur.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            cur.add(1);
            for (int size = cur.size(), j = size - 2; j >= 1; j--) {
                cur.set(j, cur.get(j - 1) + cur.get(j));
            }
        }
        return cur;
    }
}
